package summer.window;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution480 {
    // https://leetcode.cn/problems/longest-harmonious-subsequence/solutions/1111541/gong-shui-san-xie-yi-ti-shuang-jie-hua-d-quuh
    // https://leetcode.cn/problems/sliding-window-median/solutions/588643/hua-dong-chuang-kou-zhong-wei-shu-by-lee-7ai6
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        double[] doubles = medianSlidingWindow(nums, 3);
    }

    static PriorityQueue<Integer> small = new PriorityQueue<>((o1, o2) -> Integer.compare(o2,o1));
    static PriorityQueue<Integer> big = new PriorityQueue<>(Integer::compare);

    static Map<Integer, Integer> map = new HashMap<>();

    public static double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        for (int i = 0; i < k; i++) {
            add(small.size() == big.size(), nums[i]);
        }
        double[] res = new double[n - k + 1];
        res[0] = getMid(k);
        for (int i = k; i < n; i++) {
            int left = nums[i - k];
            map.put(left, map.getOrDefault(left, 0) + 1);
            add(left <= small.peek(), nums[i]);
            res[i - k + 1] = getMid(k);
        }
        return res;
    }

    public static double getMid(int k) {
        while (!small.isEmpty() && map.getOrDefault(small.peek(), 0) > 0) {
            map.put(small.peek(), map.get(small.peek()) - 1);
            small.poll();
        }
        while (!big.isEmpty() && map.getOrDefault(big.peek(), 0) > 0) {
            map.put(big.peek(), map.get(big.peek()) - 1);
            big.poll();
        }
        if ((k & 1) == 1) return small.peek() * 1.0;
        else return small.peek() / 2.0 + big.peek() / 2.0;
    }

    public static void add(boolean toSmall, int x) {
        if (toSmall) {
            big.add(x);
            small.add(big.poll());
        } else {
            small.add(x);
            big.add(small.poll());
        }
    }
}
